/*
 * Copyright (c) 2021.版权所有高金磊
 */

package 领扣算法.AA中等题.路径总和II;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class Main {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root==null){
            return new LinkedList<>();
        }
        LinkedList<List<Integer>> result=new LinkedList<>();
        HashMap<TreeNode,List<Integer>> data=new HashMap<>();
        LinkedList<Integer> list = new LinkedList<>();
        list.addLast(root.val);
        data.put(root,list);
        LinkedList<TreeNode> treeNodes=new LinkedList<>();
        treeNodes.addLast(root);
        while (!treeNodes.isEmpty())
        {
            TreeNode treeNode = treeNodes.pollFirst();
            List<Integer> middle = data.get(treeNode);
            if (treeNode.left!=null){
                LinkedList<Integer> linkedList = new LinkedList<>(middle);
                linkedList.addLast(treeNode.left.val);
                data.put(treeNode.left, linkedList);
                treeNode.left.val+=treeNode.val;
                treeNodes.addLast(treeNode.left);
            }
            if (treeNode.right!=null){
                LinkedList<Integer> linkedList = new LinkedList<>(middle);
                linkedList.addLast(treeNode.right.val);
                data.put(treeNode.right, linkedList);
                treeNode.right.val+=treeNode.val;
                treeNodes.addLast(treeNode.right);
            }
            if (treeNode.left==treeNode.right&&targetSum==treeNode.val){
                result.addLast(data.get(treeNode));
            }
        }
        return result;
    }
}
  class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
 }
